package resilienceManager.qmul.gemom;


import java.util.*;

import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.TreeNode;




/**
 * Main Auction class used for the bid
 * 
 * build the bid tree
 * 
 * search the bid tree
 * 
 * find the minimum risk  
 * 
 * COPYRIGHT DISCLAIMER
 * Synopsis: All the source codes presented in this document are intellectual
 * properties of Queen Mary, University of London.
 * 
 * @year 2010
 * @author Peng Jiang, John Bigham, Jiayi Wu Jinfu Wang------------QMUL
 * @version 1.0 
 */
 
public class BidTree {

	// the list of the items
	private static NSitem[] itemlist ;

	// the list of the bidders
	private static Gbroker[] bidders;

	// the ID of Broken gbroker
	private int bgID;

	// the value list of the items
	private int[] valuelist;

	// the default root of the bid tree
	bidNode rootNode=null;
	
	
	// the vector for saving the leaf of the tree
	private static Vector<bidNode> leafList = new Vector<bidNode>();
	
	// the risk value for the path
	private static Vector<Double> riskList = new Vector<Double>();
	
	// the linkedlist build by all the items; start from 1
	private static LinkedList<Integer> AllItems;
	
	
	// the minimum risk for the search
	public double risk_sl;


	/**
	 * constractor with the itemlist and gbroker list
	 * 
	 * gbroker list has the current 
	 * 
	 * */

	public BidTree(NSitem[] ilist, Gbroker[] glist, int id)
	{


		this.itemlist=ilist;

		this.bidders=glist;

		this.bgID = id;

		this.valuelist=new int[this.itemlist.length];

		for(int i=0; i< itemlist.length;i++)
		{
			this.valuelist[i]=itemlist[i].nslist.size();

		}
		
		AllItems = new LinkedList<Integer>();
		
		for(int i=0; i< itemlist.length;i++)
		{
			this.valuelist[i]=itemlist[i].nslist.size();
			AllItems.add(i+1);

		}
		int pause=1;
	}



	/**
	 * The main method to find all the sub set based on the linkedlist A
	 * 
	 * recursive algorithm
	 * */

	public static LinkedList<LinkedList<Integer>>  powSet(LinkedList<Integer> A)
	{	
		LinkedList<LinkedList<Integer>> ans= new LinkedList<LinkedList<Integer>> ();	
		if(A.size() == 1){//if there's only one element, we know the answer	

			ans.add(new LinkedList<Integer>());//empty set		

			LinkedList<Integer> temp= new LinkedList<Integer>();		

			temp.add(A.get(0));//and the only element in the original set	

			ans.add(temp);	

		}else{

			int first= A.remove(0);//save the first element		

			LinkedList<LinkedList<Integer>> partial= powSet(A);//recursion call		

			for(LinkedList<Integer> subset: partial) //for each set in the partial set
			{			
				//add it to the answer
				ans.add(subset);

				LinkedList<Integer> temp= new LinkedList<Integer>(subset);			
				//add the saved element to it	
				temp.add(first);
				//sort that set	
				Collections.sort(temp);	
				//add the new set to the answer
				ans.add(temp);		
			}	
		}	
		return ans;
	}



	/**
	 * according to the item list and gbroker list,build the bider tree 
	 * 
	 * */

	public void buildTree()
	{

		LinkedList<Integer> va=new LinkedList<Integer>(); 

		for(int i=0; i<itemlist.length; i++)
		{
			va.add((Integer)itemlist[i].getID());
		}

		Iterator<Integer> it=va.iterator();
		while(it.hasNext()){
			System.out.println(it.next());
		}
		
		
		LinkedList<LinkedList<Integer>> AllSet= powSet(va);

		//Allprint(AllSet);

		rootNode= new bidNode("Bid");



		for(int i=0; i<AllSet.size(); i++)
		{
System.out.println("in 1st loop "+ i + " in " +AllSet.size());
			Gbroker currentBid=bidders[0];

// the i+1 th itemset
			LinkedList<Integer> ta=AllSet.get(i);

			if(ta.size()>0)
			{
				if(currentBid.acceptAll(getValueOflist(ta)))
				{
//					name of ta, ta is the itemset
					String name="";
					for(int j=0; j<ta.size(); j++)
					{
						int id=ta.get(j)+1;
						if(j!=(ta.size()-1))
							name=name+id+"-";
						else
							name=name+id;
					}

					bidNode newNode= new bidNode(name,ta);

					rootNode.add(newNode);
					
					LinkedList<Integer> tall=getItemAbove(newNode);

					LinkedList<LinkedList<Integer>> newSet=findPoSet(AllSet, tall);				

					buildNode(newNode, newSet, 1);
				}
				else {
					System.out.println("not accepted ta broker" + ta + currentBid.getID());
				}
			}
		}




	}


	private static void buildNode(bidNode current,LinkedList<LinkedList<Integer>> PoSet, int GID )
	{

		// if reach the last bidder 
		if(GID> (bidders.length-1))
		{
//			System.out.println("GID "+ GID + " +" + bidders.length);
			leafList.add(current);
			
			riskList.add(getRiskvalue(current));
			
			return;
		}
			

		Gbroker currentBid=bidders[GID];

		for(int i=0; i< PoSet.size(); i++)
		{
			LinkedList<Integer> ta=PoSet.get(i);

			if(ta.size()>0)
			{
				if(currentBid.acceptAll(getValueOflist(ta)))
				{
					String name="";
					for(int j=0; j<ta.size(); j++)
					{
						int id=ta.get(j)+1;
						if(j!=(ta.size()-1))
							name=name+id+"-";
						else
							name=name+id;
					}

					bidNode newNode= new bidNode(name,ta);

					current.add(newNode);
					
					LinkedList<Integer> tall=getItemAbove(newNode);
				
	
					LinkedList<LinkedList<Integer>> newSet=findPoSet(PoSet, tall);

					buildNode(newNode,newSet, GID+1);
				}
			}

		}


	}


	private static LinkedList<LinkedList<Integer>> findPoSet(LinkedList<LinkedList<Integer>> PoSet, LinkedList<Integer> used)
	{

		LinkedList<LinkedList<Integer>> tem=(LinkedList<LinkedList<Integer>>) PoSet.clone();

		
		for(int i=0; i< used.size(); i++)
		{
			int itemID=used.get(i);
			tem=exceptItem(tem, itemID);
			
		}
		

		return tem;
	}


	private static LinkedList<LinkedList<Integer>> exceptItem( LinkedList<LinkedList<Integer>> AL, int itemID)
	{

		LinkedList<LinkedList<Integer>> tem=(LinkedList<LinkedList<Integer>>) AL.clone();
		LinkedList<LinkedList<Integer>> deID=new LinkedList<LinkedList<Integer>>();


			for(int i=0; i<tem.size(); i++)
			{
				LinkedList<Integer> temList=tem.get(i);

				if(temList.contains((Integer)itemID))
				{
					deID.add(temList);
				}
			}
			
			tem.removeAll(deID);
		

		return tem;
		

	}

	private void Allprint( LinkedList<LinkedList<Integer>> AL)
	{
		for(int i=0; i<AL.size(); i++)
		{
			System.out.print("Set("+i+")=[");
			for(int j=0; j<AL.get(i).size(); j++)
			{
				System.out.print(AL.get(i).get(j)+",");
			}
			System.out.println("]");
		}
	}


	private static int getValueOflist(LinkedList<Integer> la)
	{
		int value=0;


		for(int i=0; i<la.size(); i++)
		{
			value=value+itemlist[la.get(i)].nslist.size();
		}

		return value;

	}


	/**
	 * find already used list
	 * 
	 * return already used the item list
	 * */
	private static LinkedList<Integer> getItemAbove(bidNode current)
	{
		LinkedList<Integer> above = (LinkedList<Integer>) current.getBidItem().clone() ;

		bidNode currentNode=current;
		
		while(!currentNode.toString().equals("Bid"))
		{
				bidNode pNode=(bidNode) currentNode.getParent();

				if(!pNode.toString().equals("Bid"))
				{
					for(int i=0; i<pNode.getBidItem().size(); i++)
					{
						if(!above.contains(pNode.getBidItem().get(i)))
							above.add(pNode.getBidItem().get(i));
					}
					currentNode=pNode;
				}
				else
					return above;

		}

		return above;
	}


	
	


	// search the optimal path for the bid tree

	public DefaultMutableTreeNode SearchTree(){
		
		DefaultMutableTreeNode root= new DefaultMutableTreeNode("Bid");
		
		DefaultMutableTreeNode current = null;
		double minRisk=1000000;
		
		int bidID=0;
		for(int i=0; i< riskList.size(); i++)
		{
			double t=riskList.get(i);
			if((t>0)&&(t<minRisk))
			{
				minRisk=t;
				bidID=i;
			}
		}
		
		this.risk_sl=minRisk;
		System.out.println("Normal Risk="+minRisk);
		bidNode winBid=leafList.get(bidID);
		
		TreeNode[] nodelist=winBid.getPath();
		
		//System.out.println("Length="+nodelist.length);
		
		for(int i=0; i<nodelist.length; i++)
		{
			if(nodelist[i].toString().equals("Bid"))
			{
				// do nothing
				current=root;
				continue;
			}
			else
			{
				//bidNode temp=(bidNode) nodelist[i];
				
				DefaultMutableTreeNode addNode= new DefaultMutableTreeNode(nodelist[i].toString());
				current.add(addNode);
				
				current=addNode;
				
			}
		}
		
		return root;
			
	}
	
	
	// get the risk value for the bid node
	
	// return -1 mean not all the items include in the path
	
	// return >0 mean all the items are include in the path and this is the risk value for this path
	
	private static double getRiskvalue(bidNode leaf)
	{
		double risk = 0;
		
		Vector<Integer> totalItem=new Vector<Integer>();
		
		TreeNode[] nodelist=leaf.getPath();
		
		for(int i=0; i<nodelist.length; i++)
		{
			if(nodelist[i].toString().equals("Bid"))
			{
				// nothing doing
				continue;
			}
			else
			{
				bidNode temp=(bidNode) nodelist[i];
				
				for(int j=0; j<temp.getBidItem().size();j++)
				{
					totalItem.add(temp.getBidItem().get(j));
				}
//				TODO now both current and bid items are used 
/*				if(temp.getBidderItemIDs()!=null && temp.getBidderItemIDs().size()>0){
					for(int j=0; j<temp.getBidderItemIDs().size();j++)
					{
						totalItem.add(temp.getBidderItemIDs().get(j));
					}			
				}*/
				
				risk=risk+ bidders[i-1].getRisk(temp.getNodevalue(itemlist));
				
			}
		}
		
		
		if(checkTotalItem(totalItem))
		{
			return risk;
		}
		else
		{
			risk=-1;
			return risk;
		}
		
	}
	
	
	private static boolean checkTotalItem(Vector<Integer> list)
	{
		boolean allincludes=false;
		
		if(list.size()!=itemlist.length)
			return allincludes;
		
		
		for(int i=0; i<list.size(); i++)
		{
			for(int j=i+1; j< list.size(); j++)
				if(list.get(i)==list.get(j))
					return allincludes;
		}
		
		return true;
	}



	public DefaultMutableTreeNode getBidTree()
	{
	
		return (DefaultMutableTreeNode)rootNode;
	}



}
